#include <cassert>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        rows = board.size();
        cols = board[0].size();
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

private:
    int rows, cols;

    bool dfs(vector<vector<char>>& board,
             string word,
             int row,
             int col,
             int wordIndex) {
        if (row >= rows || row < 0 || col >= cols || col < 0 ||
            board[row][col] != word[wordIndex]) {
            return false;
        }

        if (wordIndex == word.size() - 1) {
            return true;
        }

        board[row][col] = '\0';  // 避免重复访问同一个字符

        bool res = dfs(board, word, row + 1, col, wordIndex + 1) ||
                   dfs(board, word, row - 1, col, wordIndex + 1) ||
                   dfs(board, word, row, col + 1, wordIndex + 1) ||
                   dfs(board, word, row, col - 1, wordIndex + 1);

        board[row][col] =
            word[wordIndex];  // 在回溯之前，将当前字符还原为原始值

        return res;
    }
};

int main() {
    Solution s;

    string word1 = "ABCCED";
    string word2 = "SEE";
    string word3 = "ABCB";

    vector<vector<char>> board{
        {'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};

    assert(s.exist(board, word1) == true);
    assert(s.exist(board, word2) == true);
    assert(s.exist(board, word3) == false);

    return 0;
}